package com.yanceysong.codetop.s61_s70;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class S67_Mid_39_组合总和 {
    /**
     * .S67_Mid_39_组合总和
     * .<p>
     * .<a href="https://leetcode.cn/problems/combination-sum/">LeetCode 39. 组合总和</a>
     * .<p>
     * .给你一个 <b>无重复元素</b> 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 <b>所有不同组合</b>，并以列表形式返回。
     * .你可以按 任意顺序 返回这些组合。 candidates 中的 <b>同一个数字可以无限次数被选取</b>。
     * .如果至少一个数字的被选数量不同，则两种组合视为不同的组合。
     * .<p>
     * .题目保证：满足和为 target 的不同组合数量少于 150 个。
     * .<p>
     * .核心标签：回溯 / 深度优先搜索 DFS / 剪枝 / 组合搜索
     * .<p>
     * .示例 1：
     * .输入：candidates = [2,3,6,7], target = 7
     * .输出：[[2,2,3],[7]]
     * .解释：2 与 3 可以组成 2+2+3=7；7 本身即为一个组合。
     * .<p>
     * .示例 2：
     * .输入：candidates = [2,3,5], target = 8
     * .输出：[[2,2,2,2],[2,3,3],[3,5]]
     * .<p>
     * .示例 3：
     * .输入：candidates = [2], target = 1
     * .输出：[]
     * .<p>
     * .示例 4：
     * .输入：candidates = [1], target = 2
     * .输出：[[1,1]]
     * .<p>
     * .示例 5：
     * .输入：candidates = [1,2], target = 3
     * .输出：[[1,1,1],[1,2]]
     * .<p>
     * .----------------------------------------
     * .解题思路（回溯模板）：
     * .1. 排序：为了方便剪枝（当当前候选值大于剩余 target 时可以直接 break）。
     * .2. 选择路径 path（本代码里使用 path 列表保存当前构建的组合）。
     * .3. 递归函数 backtrack(剩余目标, 起始下标)：从起始下标向后尝试所有候选；允许重复选当前元素，因此下一层递归仍传 i。
     * .4. 终止条件：剩余 target == 0 时，收集一个解；剩余 target < 0 时，提前剪枝返回。
     * .5. 去重策略：因为每一层的 for 都从 start 开始，而不是从 0 开始，避免了同一组合的不同排列（保证组合不重复）。
     * .<p>
     * .----------------------------------------
     * .关键洞察：
     * .- “无限重复” 与 “不可换序” 的组合问题 -> 一维组合，不记录顺序，靠 start 控制不回头，确保同一个元素的选择是非降序的，防止重复。
     * .- 排序 + 剪枝：一旦 candidates[i] > 剩余 target，可直接停止遍历后续更大的元素。
     * .- 选择树是一棵“可重复使用某个节点”的多叉树，深度由 target / 最小元素约束。
     * .<p>
     * .----------------------------------------
     * .ASCII 递归搜索树示意（candidates=[2,3,6,7], target=7）：
     * .(start=0, remain=7)
     * . ├─ 选 2 → remain=5
     * . │    ├─ 选 2 → remain=3
     * . │    │    ├─ 选 2 → remain=1 (剪枝，>1 继续选 2 会负，结束)
     * . │    │    └─ 选 3 → remain=0 ✓ 收集 [2,2,3]
     * . │    ├─ 选 3 → remain=2 (后续只能选 3/6/7，但都 >2，剪枝)
     * . │    ├─ 选 6 → remain=-1 剪枝
     * . │    └─ 选 7 → remain=-2 剪枝
     * . ├─ 选 3 → remain=4
     * . │    ├─ 选 3 → remain=1 (后续 3/6/7 >1 剪枝)
     * . │    ├─ 选 6 → remain=-2 剪枝
     * . │    └─ 选 7 → remain=-3 剪枝
     * . ├─ 选 6 → remain=1 (后续 6/7 >1 剪枝)
     * . └─ 选 7 → remain=0 ✓ 收集 [7]
     * .<p>
     * .----------------------------------------
     * .时间复杂度（近似）：受限于组合数量，最坏接近指数级。
     * .上界可以粗略认为 O(S) ，其中 S 为答案组合总数，生成每个组合需要 O(k)（k是组合长度）复制路径。题目保证 S < 150。
     * .空间复杂度：O(target / minCandidate) 递归深度 + O(S * .k) 输出存储；辅助路径最大长度不超过 target / minCandidate。
     * .<p>
     * .----------------------------------------
     * .常见边界与测试用例：
     * .- 空数组 candidates = [] -> 返回 []
     * .- target = 0 -> 返回 [[]] （本题语义一般不提供该输入；如提供逻辑上应返回一条空组合，可按需求选择，此处保持现实现行为：返回 []）
     * .- 无法凑出 target -> 返回 []
     * .- 只有一个元素，且能整除 target -> 重复该元素若干次
     * .- 包含 1 时解空间更大，注意剪枝有效性
     * .<p>
     * .----------------------------------------
     * .与类似题目的对比：
     * .- 组合总和 II（LeetCode 40）：元素可重复，但 candidates 有重复，需要去重策略；且每个元素只能使用一次。
     * .- 子集问题：不要求和为 target，也不允许重复使用元素。
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // 结果列表：存放所有满足条件的组合
        List<List<Integer>> allCombinations = new ArrayList<>();
        // 边界处理：空数组或 target < 0
        if (candidates == null || candidates.length == 0 || target < 0) {
            return allCombinations;
        }
        // 排序用于剪枝：保证后续遇到超出剩余目标的数可以直接 break
        Arrays.sort(candidates);
        // 当前构造中的组合（路径）
        List<Integer> currentCombination = new ArrayList<>();
        backtrack(currentCombination, target, candidates, 0, allCombinations);
        return allCombinations;
    }

    private void backtrack(List<Integer> currentCombination
            , int remainingTarget
            , int[] sortedCandidates
            , int startIndex
            , List<List<Integer>> allCombinations) {
        // 成功条件：剩余为 0，复制当前路径作为一个解
        if (remainingTarget == 0) {
            allCombinations.add(new ArrayList<>(currentCombination));
            return;
        }
        // 遍历所有可选分支，从 startIndex 开始，避免产生不同顺序的重复组合
        for (int i = startIndex; i < sortedCandidates.length; i++) {
            int candidateValue = sortedCandidates[i];
            int nextRemaining = remainingTarget - candidateValue;
            // 剪枝：若减去当前候选后变为负数，后续更大的数只会更负，直接停止循环
            if (nextRemaining < 0) {
                break;
            }
            // 尝试：选择当前数字，加入路径
            currentCombination.add(candidateValue);
            // 递归：因为允许重复选当前元素，下一轮仍从 i 开始（而不是 i+1）
            backtrack(currentCombination, nextRemaining, sortedCandidates, i, allCombinations);
            // 回退：撤销刚刚的选择，恢复路径状态
            currentCombination.remove(currentCombination.size() - 1);
        }
    }


    /**
     * .打印帮助函数：格式化输出一个组合列表
     */
    private static void printCombinations(List<List<Integer>> combos) {
        System.out.print("组合数量=" + combos.size() + ": [");
        for (int i = 0; i < combos.size(); i++) {
            System.out.print(combos.get(i));
            if (i != combos.size() - 1) System.out.print(", ");
        }
        System.out.println("]");
    }

    /**
     * .单个测试用例执行与校验
     */
    private static void runTestCase(String caseName, int[] candidates, int target, List<List<Integer>> expected) {
        S67_Mid_39_组合总和 solver = new S67_Mid_39_组合总和();
        List<List<Integer>> actual = solver.combinationSum(candidates, target);
        // 为了稳定比较：对内部每个组合排序（本算法保证非降序），并对外层按字典序排序
        actual.sort((a, b) -> {
            int len = Math.min(a.size(), b.size());
            for (int i = 0; i < len; i++) {
                int diff = a.get(i) - b.get(i);
                if (diff != 0) return diff;
            }
            return a.size() - b.size();
        });
        if (expected != null) {
            expected.sort((a, b) -> {
                int len = Math.min(a.size(), b.size());
                for (int i = 0; i < len; i++) {
                    int diff = a.get(i) - b.get(i);
                    if (diff != 0) return diff;
                }
                return a.size() - b.size();
            });
        }
        System.out.println("\n=== " + caseName + " ===");
        System.out.println("输入 candidates=" + Arrays.toString(candidates) + ", target=" + target);
        System.out.print("输出: ");
        printCombinations(actual);
        if (expected != null) {
            System.out.print("期望: ");
            printCombinations(expected);
            boolean pass = actual.equals(expected);
            System.out.println(pass ? "✓ 测试通过" : "✗ 测试失败");
            assert pass : "测试失败: " + caseName;
        } else {
            System.out.println("(无显式期望，用于性能或边界观察)");
        }
    }

    public static void main(String[] args) {
        // 测试用例 1：题目示例1
        runTestCase("示例1", new int[]{2, 3, 6, 7}, 7, Arrays.asList(
                Arrays.asList(2, 2, 3),
                Arrays.asList(7)));

        // 测试用例 2：题目示例2
        runTestCase("示例2", new int[]{2, 3, 5}, 8, Arrays.asList(
                Arrays.asList(2, 2, 2, 2),
                Arrays.asList(2, 3, 3),
                Arrays.asList(3, 5)));

        // 测试用例 3：题目示例3（无解）
        runTestCase("示例3", new int[]{2}, 1, Arrays.asList());

        // 测试用例 4：单元素可重复使用
        runTestCase("单元素整除", new int[]{2}, 6, Arrays.asList(
                Arrays.asList(2, 2, 2)));

        // 测试用例 5：包含 1 导致大量组合 (仅检查部分，期望列出所有)
        runTestCase("包含1的情况", new int[]{1, 2, 3}, 5, Arrays.asList(
                Arrays.asList(1, 1, 1, 1, 1),
                Arrays.asList(1, 1, 1, 2),
                Arrays.asList(1, 1, 3),
                Arrays.asList(1, 2, 2),
                Arrays.asList(2, 3)));

        // 测试用例 6：target 为 0 （期望：当前实现结果为空，因为没有进入回溯成功条件；可按需求调整）
        runTestCase("target=0", new int[]{2, 3}, 0, Arrays.asList());

        // 测试用例 7：较大 target 观察性能（不提供期望）
        runTestCase("较大目标观察", new int[]{2, 3, 5}, 15, null);

        // 测试用例 8：无候选数组
        runTestCase("空数组", new int[]{}, 7, Arrays.asList());

        // 测试用例 9：无解但多元素
        runTestCase("无解多元素", new int[]{4, 5, 11}, 3, Arrays.asList());

        // 测试用例 10：最小元素大于 target
        runTestCase("所有元素大于target", new int[]{5, 6, 7}, 4, Arrays.asList());

        System.out.println("\n=== 所有测试执行完成 ===");
    }
}
